n=100;
m=500;
price=[100,79,81,43,61,74,4,42,11,37,27,27,5,30,30,22,3,49,69,79,88,28,91,80,51,18,45,19,20,99,50,1,16,79,24,54,17,8,82,21,13,56,95,98,52,13,63,50,57,56,54,54,54,50,52,54,55,51,52,51,55,55,54,52,51,52,55,55,55,52,53,54,53,53,50,52,51,51,50,54,52,54,52,55,52,54,51,54,55,52,50,54,51,52,55,55,50,52,54,1];
roads=[|1,2,1|
1,3,1|
1,4,1|
1,5,1|
1,6,1|
4,7,1|
3,8,1|
4,9,1|
1,10,1|
6,11,1|
7,12,1|
1,13,1|
1,14,1|
9,15,1|
1,16,1|
6,17,1|
3,18,1|
18,19,1|
4,20,1|
7,21,1|
18,22,1|
15,23,1|
14,24,1|
21,25,1|
21,26,1|
23,27,1|
10,28,1|
21,29,1|
25,30,1|
12,31,1|
11,32,1|
25,33,1|
1,34,1|
5,35,1|
32,36,1|
1,37,1|
6,38,1|
20,39,1|
24,40,1|
21,41,1|
1,42,1|
5,43,1|
20,44,1|
37,45,1|
30,46,1|
11,47,1|
31,48,1|
1,49,1|
16,50,1|
2,3,1|
3,4,1|
5,6,1|
1,7,1|
4,8,1|
1,9,1|
5,11,1|
3,12,1|
4,13,1|
6,14,1|
7,15,1|
8,16,1|
2,17,1|
1,18,1|
1,19,1|
12,20,1|
1,22,1|
6,23,1|
4,24,1|
13,25,1|
20,26,1|
1,27,1|
19,28,1|
5,29,1|
16,30,1|
7,31,1|
28,32,1|
16,33,1|
19,34,1|
27,35,1|
1,36,1|
5,37,1|
13,39,1|
34,40,1|
5,41,1|
29,43,1|
6,44,1|
33,45,1|
16,46,1|
41,47,1|
36,48,1|
30,50,1|
4,6,1|
5,8,1|
5,9,1|
7,10,1|
9,12,1|
9,13,1|
12,14,1|
1,15,1|
5,16,1|
5,17,1|
8,18,1|
15,20,1|
17,21,1|
12,23,1|
10,25,1|
16,26,1|
23,28,1|
19,29,1|
12,30,1|
1,31,1|
23,32,1|
2,33,1|
16,34,1|
15,35,1|
15,36,1|
36,38,1|
12,39,1|
11,41,1|
26,42,1|
1,43,1|
11,44,1|
23,45,1|
42,46,1|
42,47,1|
11,2,2|
28,3,2|
31,4,2|
37,6,2|
30,7,2|
42,9,2|
3,10,2|
36,11,2|
50,12,2|
37,13,2|
44,14,2|
18,15,2|
20,16,2|
26,17,2|
4,18,2|
5,19,2|
37,20,2|
9,21,2|
23,22,2|
44,23,2|
30,24,2|
45,25,2|
15,26,2|
6,27,2|
24,28,2|
25,31,2|
3,32,2|
11,33,2|
44,34,2|
14,35,2|
35,36,2|
28,37,2|
7,38,2|
25,39,2|
9,40,2|
27,41,2|
18,42,2|
15,43,2|
44,45,2|
37,46,2|
17,48,2|
13,49,2|
34,50,2|
4,2,2|
14,3,2|
30,4,2|
8,6,2|
14,7,2|
30,8,2|
34,9,2|
46,10,2|
16,11,2|
17,12,2|
35,13,2|
26,14,2|
24,15,2|
9,16,2|
38,17,2|
48,18,2|
26,19,2|
11,22,2|
10,24,2|
34,25,2|
47,26,2|
47,27,2|
9,28,2|
22,29,2|
13,30,2|
29,31,2|
9,32,2|
30,33,2|
23,34,2|
42,35,2|
17,36,2|
27,38,2|
9,39,2|
48,40,2|
10,41,2|
44,42,2|
48,43,2|
22,44,2|
49,46,2|
7,47,2|
26,48,2|
38,49,2|
19,2,2|
23,4,2|
28,5,2|
36,6,2|
24,9,2|
2,10,2|
7,13,2|
8,14,2|
42,15,2|
35,16,2|
41,17,2|
30,18,2|
20,19,2|
31,20,2|
4,22,2|
18,25,2|
3,27,2|
12,29,2|
2,30,2|
27,31,2|
46,32,2|
46,33,2|
22,35,2|
8,37,2|
16,38,2|
2,39,2|
44,40,2|
2,41,2|
16,42,2|
40,43,2|
37,44,2|
2,45,2|
23,46,2|
22,47,2|
39,48,2|
40,49,2|
24,50,2|
31,2,2|
26,3,2|
12,4,2|
1,51,1|
51,52,1|
51,53,1|
51,54,1|
51,55,1|
53,56,1|
1,57,1|
55,58,1|
56,59,1|
57,60,1|
53,61,1|
61,62,1|
51,63,1|
56,64,1|
63,65,1|
51,66,1|
58,67,1|
61,68,1|
51,69,1|
53,70,1|
52,71,1|
61,72,1|
62,73,1|
73,74,1|
53,75,1|
69,76,1|
52,77,1|
1,78,1|
54,79,1|
67,80,1|
60,81,1|
60,82,1|
76,83,1|
54,84,1|
67,85,1|
76,86,1|
56,87,1|
64,88,1|
55,89,1|
65,90,1|
83,91,1|
79,92,1|
63,93,1|
81,94,1|
68,95,1|
71,96,1|
1,97,1|
97,98,1|
71,99,1|
71,100,1|
52,53,1|
55,56,1|
56,57,1|
52,58,1|
1,59,1|
51,60,1|
60,61,1|
51,62,1|
55,63,1|
58,64,1|
52,65,1|
53,66,1|
1,67,1|
55,68,1|
65,69,1|
69,70,1|
61,71,1|
65,72,1|
1,73,1|
64,74,1|
59,75,1|
71,76,1|
59,77,1|
65,78,1|
55,79,1|
57,80,1|
1,81,1|
57,82,1|
77,83,1|
67,84,1|
63,85,1|
67,86,1|
53,87,1|
83,88,1|
63,89,1|
81,90,1|
75,91,1|
51,92,1|
78,93,1|
83,94,1|
58,95,1|
62,96,1|
69,97,1|
73,98,1|
77,99,1|
93,100,1|
52,54,1|
54,55,1|
57,58,1|
58,59,1|
1,60,1|
59,61,1|
62,63,1|
59,65,1|
55,66,1|
66,67,1|
58,69,1|
63,71,1|
66,73,1|
67,75,1|
74,76,1|
58,77,1|
53,78,1|
78,79,1|
79,80,1|
63,81,1|
67,82,1|
58,83,1|
75,84,1|
59,85,1|
85,86,1|
76,87,1|
85,88,1|
59,89,1|
89,90,1|
77,65,2|
89,71,2|
90,58,2|
85,51,2|
57,70,2|
76,95,2|
64,55,2|
72,81,2|
57,51,2|
51,58,2|
63,80,2|
93,95,2|
69,98,2|
72,85,2|
78,71,2|
80,83,2|
93,80,2|
90,80,2|
82,93,2|
85,90,2|
80,65,2|
76,61,2|
88,59,2|
72,56,2|
73,53,2|
86,51,2|
89,62,2|
80,98,2|
72,58,2|
68,96,2|
92,65,2|
56,51,2|
72,83,2|
53,97,2|
75,72,2|
52,92,2|
62,90,2|
93,74,2|
51,93,2|
97,63,2|
76,64,2|
86,77,2|
87,52,2|
82,72,2|
96,75,2|
70,55,2|
78,77,2|
93,85,2|
54,81,2|
89,85,2|
51,90,2|
73,89,2|
87,80,2|
73,79,2|
71,72,2|
81,88,2|
85,82,2|
93,64,2|
72,90,2|
81,66,2|
79,62,2|
82,91,2|
58,73,2|
66,86,2|
89,67,2|
79,58,2|
67,95,2|
79,82,2|
58,91,2|
93,65,2|
88,51,2|
67,72,2|
57,79,2|
91,97,2|
90,93,2|
65,51,2|
93,55,2|
55,90,2|
88,84,2|
70,78,2|
87,55,2|
53,62,2|
94,56,2|
97,77,2|
53,84,2|
89,69,2|
63,90,2|
72,98,2|
79,64,2|
71,56,2|
56,92,2|
95,60,2|
87,62,2|
69,52,2|
87,70,2|
62,97,2|
81,62,2|
94,79,2|
84,56,2|
72,73,2|
67,91,2|
89,84,2|
68,71,2|
65,56,2|
68,75,2|
71,94,2|
65,60,2|
95,86,2|
70,79,2|
59,76,2|
76,92,2|
97,55,2|
59,83,2|
60,93,2|
63,75,2|
55,53,2|
74,78,2|
65,55,2|
78,73,2|
68,97,2|
94,77,2|
70,98,2|
69,96,2|
85,74,2|
61,57,2|];